package homework;
//作业标题(2729)
//二叉搜索树与双向链表
//
//作业内容
//将二叉搜索树转化为排序的双向链表
//https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
public class h2729 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    TreeNode preNode;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return pRootOfTree;

        TreeNode p = pRootOfTree;
        while(p.left != null) p = p.left;
        InOrder(pRootOfTree);
        return p;
    }

    private void InOrder(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return;
        InOrder(pRootOfTree.left);
        pRootOfTree.left = preNode;
        if(preNode != null) preNode.right = pRootOfTree;
        preNode = pRootOfTree;
        InOrder(pRootOfTree.right);
    }
}
